/**
 * @file     word_search.js
 * @brief    [79. 单词搜索](https://leetcode.cn/problems/word-search/)
 * @author   Zhu
 * @date     2024-11-18 20:31
 */

/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var exist = function (board, word) {
    const m = board.length,
        n = board[0].length;
    const visited = Array(m)
        .fill(0)
        .map((_) => Array(n).fill(false));

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (check(i, j, 0)) {
                return true;
            }
        }
    }

    return false;

    // is board[i][j] === word[k]
    function check(i, j, k) {
        if (
            i < 0 ||
            i >= m ||
            j < 0 ||
            j >= n ||
            board[i][j] !== word[k] ||
            visited[i][j]
        )
            return false;

        visited[i][j] = true;
        if (
            k === word.length - 1 ||
            check(i + 1, j, k + 1) ||
            check(i - 1, j, k + 1) ||
            check(i, j - 1, k + 1) ||
            check(i, j + 1, k + 1)
        )
            return true;
        visited[i][j] = false;
        return false;
    }
};
